#pragma once
#include <string>
#include <iostream>
#include "Node.h"

namespace U4
{

	class List
	{
		class Iterator
		{
		public:
			typedef Iterator self_type;
			typedef Node value_type;
			typedef Node& reference;
			typedef Node* pointer;
			typedef std::forward_iterator_tag iterator_category;
			typedef int difference_type;

			Iterator(pointer ptr) : ptr_(ptr) { } //Constructor
			self_type operator++() { self_type i = *this; ptr_ = ptr_->next; return i; }
			self_type operator++(int junk) { ptr_ = ptr_->next; return *this; }
			reference operator*() { return *ptr_; }
			pointer operator->() { return ptr_; }
			bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
			bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }

		protected:
			pointer ptr_;
		};
	private:
		Node *head;
		Node *tail;
		Node *freeHead;

	public:

		List()
		{
			head = tail = freeHead = nullptr;
		}

		List(int freeListSize)
		{
			for (int i = 0; i < freeListSize; i++)
			{
				Node *n = new Node("");
				n->next = freeHead;
				freeHead = n;
			}
		}

		~List()
		{
			clear();
			Node *n = freeHead;
			Node *d;
			while (n != nullptr)
			{
				d = n;
				n = n->next;
				delete d;
			}
		}

		void add_at_head(string data)
		{
			if (head == nullptr)
			{
				head = new Node(data);
				tail = head;
			}
			else
			{
				Node *n = new Node(data);
				n->next = head;
				head = n;
			}
		}

		void add_at_tail(string data)
		{
			if (head == nullptr)
			{
				if (freeHead != nullptr)
				{
					head = freeHead;
					tail = head;
					tail->data = data;
					freeHead = freeHead->next;
					tail->next = nullptr;
				}
				else
				{
					head = new Node(data);
					tail = head;
				}
			}
			else
			{
				if (freeHead != nullptr)
				{
					tail->next = freeHead;
					tail = tail->next;
					tail->data = data;
					freeHead = freeHead->next;
					tail->next = nullptr;
				}
				else
				{
					Node *n = new Node(data);
					tail->next = n;
					tail = tail->next;
				}
			}
		}

		// Ordered List
		//void add_at_tail(string data)
		//{
		//	if (head == nullptr)
		//	{
		//		Node *n = new Node(data);
		//		head = ptr_(n);
		//		tail = 
		//	}
		//}

		void delete_header_node()
		{
			Node *n = head;
			head = head->next;
			n->next = freeHead;
			freeHead = n;
			freeHead->data = "";

			if (head != nullptr)
				tail = head;
		}

		void clear()
		{
			while (head != nullptr)
				delete_header_node();
		}

		void print()
		{
			Node *n = head;
			while (n != nullptr)
			{
				cout << n->data << endl;
				n = n->next;
			}
		}

		Node *search(string s)
		{
			Node *n = head;
			if (n == nullptr)
				return nullptr;
			else
			{
				do
				{
					if (n->data.compare(s) == 0)
						return n;
					n = n->next;
				} while (n != nullptr);
			}

			return nullptr;
		}

		int findMax(string &ord)
		{
			int max = 0;
			string word;
			Node *n = head;
			while (n != nullptr)
			{
				if (n->antal > max)
				{
					max = n->antal;
					ord = n->data;
				}
				n = n->next;
			}
			return max;
		}

		Iterator begin()
		{
			return Iterator(head);
		}

		Iterator end()
		{
			return Iterator(nullptr);
		}

		
	};
}

